package polimi.reds.optimizer.test;

import java.util.ArrayList;

import java.util.List;
import java.util.Random;


/**
 * Class ScaleFreeTopology This class represents a scale-free topology algorithm. A
 * scale-free topology algorithm creates links between the nodes following a
 * power law probability pattern. This topology is similar to real world networks in which
 * there are hub nodes (super nodes with an other degree of neighbors) and minor nodes
 * (nodes with a low degree of neighbors).
 * 
 * @author Daniele Joseph Dubois
 */
public class ScaleFreeTopology {

	/** Nodes of the topology */
	private List<Broker> brokers;

	/** Links of the topology */
	private List<Edge> links;
	
	private Random generator;
	
	public ScaleFreeTopology(List<Broker> brokers, Random random) {
		this.brokers = brokers;
		this.generator = random;
	}
	
	/**
	 * This method creates a topology for the previously set nodes. The topology
	 * is represented as a set of links.
	 * 
	 * @param topologyParams
	 *            Initialization parameters for the current topology. It must contain
	 *            the key AceOptions.RANDOM_SEED with an arbitrary integer number and
	 *            the key AceOptions.LINKS_NUMBER with an integer number representing
	 *            the number of links.
	 *            
	 * @return Set of links representing the topology
	 */
	public List<Edge> createTopology() {
		
		Integer nlinks = brokers.size() - 1;
		
		links = new ArrayList<Edge>();

		if (brokers.size() < 2) {
			return links;
		}
		
		Integer d = 2*nlinks/brokers.size();
		List<Broker> tmpNodes = new ArrayList<Broker>(brokers);
		List<Broker> addedNodes = new ArrayList<Broker>();
		
		for (Integer i=0; i<=d; i++) {
			addedNodes.add(tmpNodes.remove(0));
		}
		
		for (Integer i=0; i<d; i++) {
			for (Integer j=i+1; j<=d; j++) {
				links.add(new Edge(addedNodes.get(i), addedNodes.get(j)));
			}
		}
		
		while (tmpNodes.size() > 0) {
			Broker sourceNode = tmpNodes.remove(0);
			Broker destinationNode = getCandidateNode(addedNodes, links);
			links.add(new Edge(sourceNode, destinationNode));
			addedNodes.add(sourceNode);
		}
		
		return links;
	}
	
	private Broker getCandidateNode(List<Broker> tmpNodes, List<Edge> tmpLinks) {
		Double p = generator.nextDouble();
		
		Double previous_p = 0.0;
		Double current_p = 0.0;
		for (Integer i=0; i<tmpNodes.size(); i++) {
			previous_p = current_p;
			current_p += getDegree(tmpNodes.get(i))/(2.0*links.size());
			
			if ((p >= previous_p) && (p <= current_p)) {
				return tmpNodes.get(i);
			}
		}
		
		return null;
	}
	
	private Integer getDegree(Broker node) {
		
		Integer degree = 0;
		
		for (Edge l:links) {
			if (l.getNode1().equals(node) || l.getNode2().equals(node)) {
				degree++;
			}
		}
		
		return degree;
	}
}